Due Mar 23, 3:59 AM EDT
Seven schoolchildren were playing a chess tournament in one round (each plays one game with each). Before the lunch break Ivan played 6 games, Anatoly played 5 games, Alex and Dmitry played 3 games each, Simon and Ilya played 2 games each, and Eugene played only one game. Whom did Alex play with before the lunch break? (Select all correct answers.)
For which set of vertex degrees (these are complete lists, no extra vertices allowed) a graph with such degrees does not exist? (Select all correct answers.)
Such a graph would violate Handshaking Lemma: the sum of degrees here is 121, which is odd.
Though Handshaking Lemma is satisfied (1+2+2+3+5+5=18 is even), there is no graph with such vertex degrees. (We do not consider multigraphs or pseudographs here.) The reason is as follows: the total number of vertices is 6, thus the two vertices of degree 5 should be connected to all other vertices. Contradiction: the vertex of degree 1 could not be connected to two vertices.
How many games did the schoolchildren from Question 1 play before lunch? Recall that Ivan played 6 games, Anatoly played 5 games, Alex and Dmitry played 3 games each, Simon and Ilya played 2 games each, and Eugene played only one game.
The number of edges in a graph (games played) is counted by summing degrees of vertices: 6+5+3+3+2+2+1=22 and dividing by 2.